Counting Sets: Problems and Proofs

Let $S$ be the set of all infinite sequences of 0s and 1s. Show that $S$ is uncountable.
Proof: Use Cantor's diagonal argument.
Assume (for contradiction) that we have an enumeration of the elements of $S$; let it be $S$ = {$s_1, s_2, s_3,...$} where each $s_n$ is an infinite sequence of 0s and 1s. We'll write $s_1 = s_{1,1}, s_{1,2}, s_{1,3},...$, $s_2 = s_{2,1}, s_{2,2}, s_{2,3}, ...$, and so on. So $s_n = s_{n,1}, s_{n,2}, s_{n,3}, ...$. We denote the $m^{th}$ element of $s_n$ by $s_{n,m}$. Construct a new sequence $t = t_1, t_2, t_3,...$ of 0s and 1s as follows: $t_n = s_{n,n} - 1$. $t$ is an element of $S$, since it is an infinite sequence of 0s and 1s. However, $t$ cannot be in the enumeration above. Suppose that $t = s_k$ for some value of $k$. Then $t_k = s_{k,k}$. However, by consutrction, $t_k neq s_{k,k}$. Since this is a contradiction, we can conclude that $S$ is not countable.

Let $S$ be the set of all finite subsets of $\mathbb{N}$. Show that $S$ is countable.
Proof: Construct an injective function $f$ from $S \to \mathbb{N}$. Let $p_1, p_2, p_3,...$ be a sequence of primes in ascending order. For any finite subset $T \subseteq \mathbb{N}$, start by ordering the elements of $T$ in ascending order, $T = {t_1, t_2, t_3, ...}$, which $t_1 < t_2 < t_3 < ... < t_n$. Let $f(T) = p_1^{t_1} \bullet p_2^{t_2} \bullet... \bullet p_n^{t_n}$.
To check that $f$ is injective, suppose that $f(T) = f(T\prime)$. Then $p_1^{t_1} \bullet p_2^{t_2} \bullet ... p_n^{t_n} = p\prime_1^{t_1} \bullet p\prime_2^{t_2} \bullet ... p\prime_n^{t_n}$. By the fundamental theorem of arithmetic these two products can only be equal if $n = n\prime$ and each of the corresponding powers is equal.

4.11 The countable union of countable sets is countable
Proof: Consider some countable sets $X_0, X_1, X_2,...$ where $X = \underset{i \in \mathbb{N}}{\bigcup} X_i$.
Suppose these are all disjoint sets. Otherwise, we can consider the sets $X\prime_0 = X_0, X\prime_1 = X_1 \setminus X_0, X\prime_2 = X_2 \setminus (X_0 \cup X_1)...$. All of these are countable, since we know that a subset of a countable set is countable, and they have the same union $X$.

Construct the possibly infinite table by writing the elements of $X_0, X_1, X_2,...$ in the folling pattern:

$a_{00}$ $a_{01}$ $a_{02}$ ...
$a_{10}$ $a_{11}$ $a_{12}$ ...
$a_{20}$ $a_{21}$ $a_{22}$ ...
...

where $a_{ij}$ is the $j^{th}$ element of set $X_i$. The table contains all the elements of $X = \underset{i \in \mathbb{N}}{\bigcup} X_i$.

$f: X \to \mathbb{N} \times \mathbb{N}$ such that $a_{ij} \mapsto (i, j)$ is an injection.
Since the cartesian product of countable sets is countable, there exists an injection $g: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
So, $g \circ f: X \to \mathbb{N}$ is also an injection (since the composition of inecjtions is an injection).
So $X$ is countable.

4.18 Let $S$ be the set of all surjective functions from the set of positive integers to the set $\{0, 1\}$. Show that $S$ is uncountable.
Proof Idea: Let $S = \{f: \mathbb{Z}^+ \to \{0, 1\}\}$. Let $g = \mathbb{N} \to S$ be some function. Let's show that $g$ is not bijective (in particular, it is not surjective).

Define $f_g: \mathbb{N} \to \{0, 1\}$ as follows:

$f_g(n) = \begin{cases} 0 \text{ if } (g(n))(n) = 1, \\ 1 \text{ if } (g(n))(n) = 0 \end{cases}$

Note that this makes $g(n) \in S$, so $g(n)$ is a function $\mathbb{N} \to S$. So we can evaluate $g(n)$ at any positive integer and obtain either $0$ or $1$. So $(g(n))(n)$ is either $0$ or $1$.

Show that $f_g \in S$ but $f_g \neq g(m)$ for every $m \in \mathbb{N}$. So $g$ is not surjective.